/**
 * 字符串拼接
 * 
 * 题目描述

给定 M（0 < M ≤ 30）个字符（a-z），从中取出任意字符（每个字符只能用一次）拼接成长度为 N（0 < N ≤ 5）的字符串，

要求相同的字符不能相邻，计算出给定的字符列表能拼接出多少种满足条件的字符串，

输入非法或者无法拼接出满足条件的字符串则返回0。

输入描述
给定的字符列表和结果字符串长度，中间使用空格(" ")拼接

输出描述
满足条件的字符串个数

用例
输入	abc 1
输出	3
说明	给定的字符为a,b,c，结果字符串长度为1，可以拼接成a,b,c，共3种
输入	dde 2
输出	2
说明	给定的字符为dde，结果字符串长度为2，可以拼接成de,ed，共2种

 */

import java.util.Arrays;
import java.util.Scanner;

/**
  * 

  题目解析
根据用例2的说明来看，本题是要求解的是：不重复的指定长度的排列。且本题还增加了一个条件，即排列中相邻元素不能相同。

本题的基础是求解排列。关于排列的求解可以看下：

LeetCode - 46 全排列_全排列 46 力扣-CSDN博客

了解的排列的求解后，我们就可以进一步了解不重复的排列求解，具体可以看下：

LeetCode - 47 全排列 II_leetcode 全排列2-CSDN博客

而本题只需要在这两题的基础增加：排列中相邻元素不能相同即可。

另一种思路，输入的字符串转换成 char[] 并去重。计算 组合 A 上 位数 下 char[]数组长度

  */
public class 字符串拼接 {
    
    public static void main(String[] args) {

        try{

            Scanner scanner = new Scanner(System.in);

            //字符串
            String inputStr = scanner.next();
            //目标字符串位数
            int targetLen = scanner.nextInt();

            if(inputStr.length() < targetLen){

                System.out.println(""+0);

                return;
            }

            char[] inputCharArr = inputStr.toCharArray();

            for(char c : inputCharArr){

                if(c < 'a' || c > 'z'){

                    //非法输入
                    System.out.println(""+0);
                    return;

                }
            }

            //排序
            Arrays.sort(inputCharArr);

            int count = dfs(inputCharArr, -1, 0, new boolean[inputCharArr.length], 0, targetLen);

            System.out.println(count);


        }catch(Exception e){

            e.printStackTrace();
        }
    }

    private static int dfs(char[] cArr, int pre, int level, boolean[] used, int count, int targetLen){

        //当排列长度到达n，则是一个符合要求的排列
        if(targetLen == level){

            return ++count;
        }

        for(int i=0; i<cArr.length; i++){

            // 每个字符只能用一次
            if(used[i]) continue;

            //相同的字符不能相邻， pre指向前面一个被选择的字符的在cArr中的位置，i指向当前被选择的字符在cArr中的位置
            if (pre >= 0 && cArr[i] == cArr[pre]) continue;

            //树层去重(去除重复排列)
            if (i > 0 && cArr[i] == cArr[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            count = dfs(cArr, i, level+1, used, count, targetLen);
            used[i] = false;
        }


        return count;

    }
}
